import java.util.*;
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
public class Text {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> cur = new ArrayList<>();
            while(size != 0) {
                TreeNode tmp = queue.poll();
                cur.add(tmp.val);
                if(tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                }
                size--;
            }
            ret.add(cur);
        }
        return ret;
    }
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int maxleft = maxDepth(root.left);
        int maxright = maxDepth(root.right);
        return (maxleft>maxright)?(maxleft+1):(maxright+1);
    }
    public boolean isSymmetric(TreeNode root) {
        return isSamary(root.left,root.right);
    }
    private boolean isSamary(TreeNode p,TreeNode q) {
        if(p == null && q != null || p != null && q == null) {
            return false;
        }
        if(p == null && q == null) {
            return true;
        }
        if(p.val != q.val) {
            return false;
        }
        return isSamary(p.left,q.right) && isSamary(p.right,q.left);
    }
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    int sum = 0;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return false;
        }
        sum += root.val;
        if(sum == targetSum && root.left == null && root.right == null) {
            return true;
        }
        boolean flagL = hasPathSum(root.left,targetSum);
        if(flagL == true) {
            return true;
        }
        boolean flagR = hasPathSum(root.right,targetSum);
        if(flagR == true) {
            return true;
        }
        sum -= root.val;
        return false;
    }
}
